package com.dubious.interview.euler;

import org.joda.time.DateTime;

import com.dubious.interview.euler.prime.SievePrimeIterator;

public class Problem7 {

    public static long run(long n) {
        System.out.println("Start Time: " + new DateTime());

        // algorithm to enumerage primes: Sieve of Eratosthenes

        // from
        // http://www.jstor.org/discover/10.2307/2371291?uid=3738016&uid=2&uid=4&sid=47698770743267
        // we know that there is an upperbound to the nth prime which is:
        // n*log(n) + n*log(log(n)) + 2n for n >= 55.

        long upperBound = calculatePrimeUpperBound(n);
        System.out.println("Upper bound " + upperBound);
        
        int i = 1;
        for(Long prime : new SievePrimeIterator(upperBound))
        {
            if(i == n)
            {
                return prime;
            }
            i++;
        }
        return -1L;
    }

    public static long calculatePrimeUpperBound(long n) {
        if (n < 55) {
            return 257;
        }

        return (long) (n * Math.log(n) + n * Math.log(Math.log(n)) + 2 * n);
    }
}
